# 暴力解法
class Solution:
    def bulbSwitch(self, n: int) -> int:
        if n == 0:
            return 0
        ans = n
        flag = [True] * n # 第一轮默认都是开的
        for i in range(1, n):  # 循环n轮
            for j in range(1, n + 1): # 判断每一个灯泡情况
                if j % (i + 1) == 0 and flag[j - 1]:
                    flag[j - 1] = False
                    ans -= 1
                elif j % (i + 1) == 0 and flag[j - 1] == False:
                    flag[j - 1] = True
                    ans += 1
        return ans
# 数学
class Solution:
    def bulbSwitch(self, n: int) -> int:
        # 找完全平方数的个数
        return int(sqrt(n + 0.5))